정보과학회 컴퓨팅의 실제 논문지 (KIISE Transactions on Computing Practices)
Current Result Document :
| 한글제목(Korean Title) |
LVS-Cache: Low-Degree Vertex Static Cache를 통한 디스크 기반 그래프 엔진 성능 향상 |
| 영문제목(English Title) |
LVS-Cache: Performance Improvement using Low-Degree Vertex Static Caching on Disk-based Graph Engine |
| 저자(Author) |
김정현
이은재
임근학
서지원
노삼혁
Junghyun Kim
Eunjae Lee
Keunhak Lim
Jiwon Seo
Sam H. Noh
김정현
이은재
임근학
서지원
노삼혁
Junghyun Kim
Eunjae Lee
Keunhak Lim
Jiwon Seo
Sam H. Noh
|
| 원문수록처(Citation) |
VOL 24 NO. 11 PP. 0628 ~ 0633 (2018. 11) |
한글내용
(Korean Abstract) |
웹과 소셜 네트워크의 발전에 따라 대규모 그래프를 효과적으로 처리하는 기법에 대한 연구가 활발히 진행되고 있다. 그 중, 단일 머신에서 작은 메모리로도 그래프 처리가 가능한, 디스크 기반 그래프 엔진이 많이 활용되고 있다. 하지만 이 엔진은 디스크 입출력 성능으로 인한 전체 프로세싱 성능 저하가 있다. 기존의 시스템은 블록 캐시를 활용하여 이러한 문제를 해결하고자 하였으나, 그래프 처리의 특성상, 블록 캐시는 캐시 적중률이 낮아 효율성이 떨어지고, 동적으로 할당하고 해제하는 비용이 발생한다. 본 논문에서는 해당 문제의 해결책으로 LVS-Cache 기법을 제안한다. 이 기법은 블록 캐시의 효율성을 저하시키는 데이터를 미리 정적으로 캐싱한다. Degree가 낮은 Vertex들을 캐싱함으로써, 메모리 사용량 대비 높은 캐시 활용 효과를 얻고자 하였다. 제안한 LVS-Cache 에 대한 실험 결과, 블록 캐시에 비해 성능이 향상되었으며, 디스크 입출력 양도 효과적으로 줄어든 것을 확인하였다.
|
영문내용
(English Abstract) |
Advancements in the web and social network have led to the flooding of large-scale graph data. Recently, researches to efficiently deal with such a big-data were proposed. Among them, disk-based graph engines were designed to process large-scale graphs on a single machine. These engines can process large-scale graph using small memory consumption. However, the engines should read graph data from disk, so disk I/O performance is critical for the whole graph processing performance. The state-of-the-art systems have proposed block-cache to reduce the direct I/O to disk. However, because of the characteristics of graph processing, the hit ratio of block-cache is low, which means that the utilization of block-cache is not good. Moreover, because it's also "cache", it needs dynamic allocation and eviction cost. In this paper, we propose LVS-Cache (Low-Degree Vertex Static Cache) to optimize disk I/O performance. LVS-Cache allocates vertices statically that degrades block-cache's utilization. Among the vertices that need to be allocated to LVS-Cache, we have chosen low-degree vertices as prior ones which have higher cache utilization in proportion to memory consumption. The result reveals improvement in performance compared to block-cache and reduction in the amount of I/O request to disk.
|
| 키워드(Keyword) |
그래프 엔진
그래프 처리
대규모 그래프
캐싱 정책
graph engine
graph processing
large-scale graph
caching policy
그래프 엔진
그래프 처리
대규모 그래프
캐싱 정책
graph engine
graph processing
large-scale graph
caching policy
|
| 파일첨부 |
PDF 다운로드
|
